Message encryption algorithms have been known for a long time, especially block encryption algorithms such as the DES (Data Encryption Standard) algorithm (now obsolete) that uses a 56-bit key, the Triple DES algorithm (made public by IBM in 1999), which uses three such keys, and the AES (Advanced Encryption Standard) algorithm selected in the United States of America in October 2000 by the NIST (National Institute of Standards and Technology), which uses keys comprising 128, 192 or 256 bits.
Most known algorithms are symmetrical algorithms, i.e. algorithms such that the entity that encrypts the message and the entity that decrypts it share the same secret key. Symmetrical algorithms have the drawback that the key must be chosen or communicated from one entity to another securely to prevent an attacker discovering it; given the required key length (at least 128 bits), the precautions that this imposes represent a severe constraint.
Attempts have therefore been made to construct asymmetrical encryption algorithms, i.e. algorithms such that any entity seeking to send an encrypted message to a particular destination can use a public variant of that algorithm that is characteristic of the addressee but such that only the addressee can decrypt the encrypted message; note that, strictly speaking, even the sender of an asymmetrically encrypted message cannot decrypt the encrypted message (it is assumed of course that the sender knows the initial message in clear). Since the encryption algorithm is accessible to all, no security precautions are required in terms of the agreement between the sender of a message and its addressee.
Note further that most asymmetrical algorithms can be used either to encrypt messages or to sign messages, these two protocols being simply the inverses of each other. In other words, for encryption applications the public key is used for encryption and the secret key is used for decryption whereas for electronic signature applications the secret key is used for signing and the public key is used to verify the signature.
In asymmetrical algorithms in which the secret key is a “trap-door” (for example the “unbalanced oil and vinegar” algorithm described below), applying an electronic signature proceeds as follows: on signing a sequence C (which can be a summary of an original document), the signatory uses the same (secret) algorithm as if this sequence C were an encrypted message to be decrypted. Thus a “signature” M obtained in this way is made available to the public, or at least to a signature verifier, at the same time as the original document. To verify this signature M thereafter, the signature verifier applies to the sequence M the same public algorithm as if it were a question of encrypting this sequence M; if the signature is authentic, the signature verifier obtains a sequence identical to the sequence C, i.e. to the original document made available to them or its summary.
The best-known asymmetrical algorithm is undoubtedly the RSA algorithm (for a detailed description of the RSA algorithm see the paper by R. L. Rivest, A. Shamir, and L. M. Adleman entitled “A Method for Obtaining Digital Signatures and Public-key Cryptosystems”, Communications of the ACM, volume 21, no. 2, pages 120 to 126, 1978). Also known are algorithms using elliptic curves (see for example the paper by Neal Koblitz entitled “Elliptic-Curve Cryptosystems”, Mathematics of Computation, volume 48, pages 203 to 209, 1987, or the paper by V. Miller entitled “Use of Elliptic Curves in Cryptography”, CRYPTO 85, 1985). Those algorithms have the drawback of requiring very burdensome calculations.
In the “unbalanced oil and vinegar” scheme proposed by A. Kipnis, J. Patarin, and L. Goubin (see their paper entitled “Unbalanced Oil and Vinegar Signature Schemes”, EUROCRYPT 1999, pages 206 to 222), the public key consists in a system of h multivariate quadratic polynomials with n variables x1 to xn, where n>h>1, over a finite field K. These polynomials are therefore of the following form:
            ∑              1        ≤        i        ≤        j        ≤        n              ⁢                  ⁢                  a        k                  (          ij          )                    ⁢              x        i            ⁢              x        j              +            ∑              1        ≤        i        ≤        n                                  ⁢                  ⁢                  β        k        i            ⁢              x        i              +            γ      k        ⁡          (              1        ≤        k        ≤        h            )      in which the coefficients αk(ij), βk(i), and γk belong to K.
This scheme uses a “trap-door” as a “secret key”. This trap-door consists in mixing two types of variables, called “oil” variables and “vinegars” variables, to constitute a system of h multivariate quadratic equations with n=ν+h variables, where the integer ν denotes the number of vinegar variables and the integer h denotes the number of oil variables. The requirement is that ν>h; moreover, each polynomial of the system includes all possible mononomials, the coefficients of which are drawn randomly, except for mononomials consisting of the product of two oil variables, which are absent. The trap-door of this method exploits the fact that a linear random system with h equations and h unknowns has a very high probability of having a unique solution. By setting randomly the value of the ν vinegar variables, it is possible to solve the resulting linear system in the h oil variables. If, for a given random choice of vinegar variables the resulting system is not invertible, it suffices to effect another random choice of vinegar variables.
To mask the structure from the public, there is applied at the input of the system a change of invertible variables from (ν+h) variables to (ν+h) variables. The system transformed in this way constitutes the public key, while the change of variables and the original system constitute the secret key.
This scheme has the drawback that it can serve only as a signature algorithm and not as an encryption algorithm. Furthermore, it is ineffective because of the necessity on signing to add to the oil variables (directly associated with the message to be signed) a great number of additional variables (the vinegar variables).
Other known asymmetrical algorithms have been cracked, for example the “C*” algorithm (see the paper by Tsutomu Matsumoto and Hideki Imai entitled “Public Quadratic Polynomial Tuples for Efficient Signature Verification and Message Encryption”, Eurocrypt '88, pages 419 to 453).